//给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。 
//
// 注意：如果对空文本输入退格字符，文本继续为空。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "ab#c", t = "ad#c"
//输出：true
//解释：s 和 t 都会变成 "ac"。
// 
//
// 示例 2： 
//
// 
//输入：s = "ab##", t = "c#d#"
//输出：true
//解释：s 和 t 都会变成 ""。
// 
//
// 示例 3： 
//
// 
//输入：s = "a#c", t = "b"
//输出：false
//解释：s 会变成 "c"，但 t 仍然是 "b"。 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length, t.length <= 200 
// s 和 t 只含有小写字母以及字符 '#' 
// 
//
// 
//
// 进阶： 
//
// 
// 你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？ 
// 
// Related Topics 栈 双指针 字符串 模拟 👍 388 👎 0

package leetcode.editor.cn;

class BackspaceStringCompare {
    public static void main(String[] args) {
        Solution solution = new BackspaceStringCompare().new Solution();
        solution.backspaceCompare("a##c", "a#c#");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
    /*public boolean backspaceCompare(String s, String t) {
        return change(s).equals(change(t));
    }*/

        /*public String change(String s) {
            int index = 0;
            // 先转化为数组
            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                // 如果不为#则赋值
                if (chars[i] != '#') {
                    chars[index++] = chars[i];
                }
                // 如果为#号，且index在不在第一个位置则进行回退
                else if (chars[i] == '#' && index != 0) {
                    index--;
                }
            }
            // 注意截取，并转化为字符串
            return String.valueOf(chars, 0, index);
        }*/

        // TODO 快慢指针
        public boolean backspaceCompare(String s, String t) {
            return change(s).equals(change(t));
        }

        public String change(String s) {
            char[] chars = s.toCharArray();
            int slowIndex = 0, fastIndex = 0;
            while (fastIndex < chars.length) {
                if (chars[fastIndex] == '#' && slowIndex != 0) {
                    slowIndex--;
                } else if (chars[fastIndex] != '#') {
                    chars[slowIndex++] = chars[fastIndex];
                }
                fastIndex++;
            }
            return String.valueOf(chars, 0, slowIndex);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
